#include "DoubleLinkList.h"
#include "LinkStack.h"
#include "LinkQueue.h"
#include <stdio.h>
#include <stdlib.h>

// void PrintInt(void *ptr)
// {
//     printf("%ld ",(long)ptr);
// }

// //删除某个数的整数倍
// bool IsOper(void *ptr1,void *ptr2)
// {
//     long a = (long)ptr1;
//     long b = (long)ptr2;

//     if(a % b == 0)
//         return true;
//     return false;
// }

// bool IsBigger(void *ptr1,void *ptr2)
// {
//     long a = (long)ptr1;
//     long b = (long)ptr2;
//     return a < b;
// }

// int main()
// {
    // INITDLLIST(list);
    // for(long i = 1; i <= 10; i++)
    // {
    //     InsertDLlistHead(&list,(void*)i);
    // }
    // TravelDLlist(&list,PrintInt);
    // //RemoveByIndex(&list,9,NULL);
    // //RemoveByElement(&list,(void*)3,IsOper,NULL);
    // //TravelDLlist(&list,PrintInt);
    // DLlistSort(&list,IsBigger);
    // TravelDLlist(&list,PrintInt);

    // printf("value : %ld \n",(long)*FindByIndex(&list,1));
    // DLlist result = FindByElement(&list,(void *)2,IsOper);
    // TravelDLlist(&result,PrintInt);

    // LStack *s = InitLStack();
    // for(long i = 1; i <= 10; i++)
    // {
    //     SPush(s,(void*)i);
    // }

    // while(IsStackEmpty(s) == false)
    // {
    //     printf("%ld ",(long)*GetSPop(s));
    //     SPop(s);
    // }
    // printf("\n");

    // ClearLStack(s,NULL);


//     LQueue *q = InitLQueue();
//     for(long i = 1; i <= 31; i++)
//     {
//         QPush(q,(void*)i);
//     }
//     int count = 0;
//     while(GetQueueLen(q) > 1)
//     {
//         count++;
//         long number = (long)*GetQFront(q);
//         QPop(q);

//         if(count == 3)
//         {
//             printf("%ld号被嘎掉!\n",number);
//             count = 0;
//         }
//         else
//         {
//             QPush(q,(void*)number);
//         }
//     }
//     printf("%ld号活了下来!\n",(long)*GetQFront(q));
//     ClearLQueue(q,NULL);
//     return 0;
// }

//判断是否是数字
bool IsNumber(char c)
{
    if(c <= '9' && c >= '0')
        return true;
    return false;
}

//判断运算符
bool IsOper(char c)
{
    switch (c)
    {
    case '+':
    case '-':
    case '*':
    case '/':
    case '(':
    case ')':
    case '=':
        return true;
    
    default:
        break;
    }
    return false;
}

//计算
int Operate(int prev,int next,char c)
{
    switch (c)
    {
    case '+':return prev + next;
    case '-':return prev - next;
    case '*':return prev * next;
    case '/':
        if(next == 0)
        {
            printf("除数为0,异常!\n");
            //退出程序
            exit(-1);
        }
        return 1.0 * prev / next;
    default:
        printf("表达式有误");
        exit(-1);
    }
}

//运算符的优先级
char Precade(char c1,char c2)
{
    char pre[7][7] = 
    // + - * / ( ) =
    {   //+   -   *   /   (   )   =
        {'>','>','<','<','<','>','>'},  //  +
        {'>','>','<','<','<','>','>'},  //  -
        {'>','>','>','>','<','>','>'},  //  *
        {'>','>','>','>','<','>','>'},  //  /
        {'<','<','<','<','<','=','0'},  //  (
        {'>','>','>','>','0','>','>'},  //  )
        {'<','<','<','<','<','0','='},  //  =
    };
    int i = 0; 
    switch (c1)
    {
    case '+':i = 0;break;
    case '-':i = 1;break;
    case '*':i = 2;break;
    case '/':i = 3;break;
    case '(':i = 4;break;
    case ')':i = 5;break;
    case '=':i = 6;break;
    default:
        break;
    }

    int j = 0;
    switch (c2)
    {
    case '+':j = 0;break;
    case '-':j = 1;break;
    case '*':j = 2;break;
    case '/':j = 3;break;
    case '(':j = 4;break;
    case ')':j = 5;break;
    case '=':j = 6;break;
    default:
        break;
    }
    return pre[i][j];
}

int main()
{
    //数据栈
    LStack *NumS = InitLStack();
    //符号栈
    LStack *operS = InitLStack();
    SPush(operS,(void*)'=');

    char str[100] = {0};
    printf("请输入一个表达式:\n");
    scanf("%s",str);

    //计数器
    int i = 0;
    while(str[i] != '\0')
    {
        //是数字
        if(IsNumber(str[i]) == true)
        {
            long n = str[i] - '0';
            i++;
            while(IsNumber(str[i]) == true)
            {
                n = n * 10 + str[i] - '0';
                i++;
            }
            SPush(NumS,(void*)n);
        }
        else if(IsOper(str[i]) == true)
        {
            switch (Precade((char)*GetSTop(operS),str[i]))
            {
            //栈顶符号优先级比拿到的大
            case '>':
                //先拿出后一个数
                long next = (long)*GetSTop(NumS);
                SPop(NumS);
                //再拿出前一个数
                long prev = (long)*GetSTop(NumS);
                SPop(NumS);

                char symbol = (char)*GetSTop(operS);
                SPop(operS);

                long result = Operate(prev,next,symbol);
                SPush(NumS,(void*)result);
                break;
            case '<':
                SPush(operS,(void*)str[i]);
                i++;
                break;
            case '=':
                SPop(operS);
                i++;
                break;
            default:
                printf("表达式有错误!\n");
                exit(-1);
            }
        }
    }
    printf("结果是%ld\n",(long)*GetSTop(NumS));
    return 0;
}